package com.ljy.my_study.lintcode.询问冷却时间;

import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;

/** 
* @author James
* @date 2018年10月17日 
*/
public class TestMain {
//	描述
//	你有一串的技能需要释放，释放顺序为arr。必须按照顺序释放。每个技能都有长度为n的冷却时间。也就是说，两个同类技能之间至少要间隔n秒。释放每个技能需要1秒,返回放完所有技能所需要的时间。
//
//	数组长度不超过100000。
//	1 \leq n \leq 201≤n≤20
//	技能的编号是不超过100的正整数。
//	您在真实的面试中是否遇到过这个题？  
//	样例
//	Given arr=[1,1,2,2],n=2.Return 8.
//
//	The order is [1, _, _, 1, 2, _, _, 2].So return 8.
//	Skill 1 is released in the 1st second, in the 2nd second and the 3rd second enters the cooling time, and the 4th second releases the second time.
//	Skill 2 is released in the 5th second, in the 6th second and the 7th second enters the cooling time, and the 8th second releases the second time.
//
//	Given arr=[1,2,1,2], n=2. Return 5.
//
//	The order is [1, 2, _, 1, 2].So return  5.
//	Skill 1 is released in the 1st second, in the 2nd second and the 3rd second enters the cooling time, and the 4th second releases the second time.
//	Skill 2 is released in the 2nd second, in the 3rd second and the 4th second enters the cooling time, and the 5th second releases the second time.
	public static void main(String[] args) {
		System.out.println(askForCoolingTime(new int[] {1,2,3,1,2,1},3));
	}
	
	public static int askForCoolingTime(int[] arr, int n) {
		int sumTime=0;
		Map<Integer,Integer> map=new HashMap<>();
		for(int i=0;i<arr.length;i++) {
			for(Entry<Integer,Integer> e:map.entrySet()) {
				Integer eVal=e.getValue();
				if(e!=null&&!e.getKey().equals(arr[i])) {
					e.setValue(eVal-1>0?eVal-1:0);
				}
			}
			Integer val=map.get(arr[i]);
			if(val==null||val==0) {
				map.put(arr[i], n);
			}else {
				sumTime+=val;
				for(Entry<Integer,Integer> e:map.entrySet()) {
					Integer eVal=e.getValue();
					if(e!=null) {
						e.setValue(eVal-val>0?eVal-val:0);
					}
				}
			}
			sumTime++;
			map.put(arr[i], n);
		}
		return sumTime;
	}
}
